package leecode

import (
	"sort"
)

func constructMaximumBinaryTree(nums []int) *TreeNode {
	var maxTree func(nums []int) (result *TreeNode)
	maxTree = func(nums []int) (result *TreeNode) {
		if len(nums) == 1 {
			result = &TreeNode{Val: nums[0]}
			return
		}
		copyNums := make([]int, len(nums), len(nums))
		copy(copyNums, nums)
		sort.Ints(copyNums)
		maxNum := copyNums[len(copyNums)-1]
		var index int
		//找到元素最大的位置的下标
		for i := 0; i < len(nums); i++ {
			if nums[i] == maxNum {
				index = i
				break
			}
		}
		result = &TreeNode{Val: maxNum}
		//切割nums数组
		if index > 0 {
			//最大值所在的下标的左区间
			leftTree := nums[:index]
			result.Left = maxTree(leftTree)
		}
		if index < (len(nums) - 1) {
			rightTree := nums[index+1:]
			result.Right = maxTree(rightTree)
		}
		return
	}
	return maxTree(nums)
}
